package org.example.tree;

import java.util.*;

/**
 * 力扣===树练习题
 * @Author chaigq
 * @Date 2020/11/23 下午11:47
 * @Version 1.0
 */
public class LeetCodeTree {

    /**
     * 树中距离之和
     *
     * 给定一个无向、连通的树。树中有 N 个标记为 0...N-1 的节点以及 N-1 条边 。
     *
     *  第 i 条边连接节点 edges[i][0] 和 edges[i][1] 。
     *  返回一个表示节点 i 与其他所有节点距离之和的列表 ans。
     *
     *  示例 1:
     * 输入: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
     * 输出: [8,12,6,10,10,10]
     * 解释:
     * 如下为给定的树的示意图：
     *   0
     *  / \
     * 1   2
     *    /|\
     *   3 4 5
     *
     * 我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
     * 也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。
     *
     *  说明: 1 <= N <= 10000
     *  Related Topics 树 深度优先搜索
     */
    // 回溯法-深度优先遍历和广度优先遍历
    // （回溯）深度优先遍历：深度优先遍历的特点我们利用Java集合类的栈Stack先进后出的特点来实现
    // 广度优先遍历：我们利用Java数据结构队列Queue来实现

    // TODO 求出每个节点为根节点的时候，它与其他所有节点的距离之和
    // TODO 思路：
    // 对于本题，一个比较直观的思路是对于每个结点作为树根，求其他所有结点到该节点的距离。复杂度为O(N*N)，很显然无法通过这道题，
    // 一个比较巧妙的思路是我们考虑两个直接相连的节点，假设为x和y，倘若我们将连接这两个点的边减掉，则会得到两棵子树，
    // 此时我们求其他所有点到x和y的距离，我们用公式表示出来：ans[x]=subSum(x)+subSum(y)+count(y)；（所有的节点到x的距离）
    // 解析：其中ans[x]为该节点的答案，subSum(x)表示删掉呢条边后以x为树根的子树中其他节点到x的距离和，count(x)表示该字数的节点个数
    // 同理：ans[y]=subSum(y)+subSum(x)+count(x);（所有的节点到y的距离）
    // TODO 我们将上述俩式相减可以得到：ans[x]-ans[y]=count(y)-count(x)，此时我们得到了相邻两个节点所求答案之间的关系。

    int[] count, ans;
    int num;
    List<List<Integer>> list;
    public int[] sumOfDistancesInTree(int N, int[][] edges) {
        // 具体实现：我们考虑两次dfs，以0节点为树根进行遍历，
        // 第一次遍历我们可以求得整棵树中以0节点为根从上往下遍历中所有子树的subSum值和count值，
        // 对于第二次遍历，我们可以通过上述求得的两个直接相连节点之间的关系从而求得最终我们所要的ans值。
        num = N;
        ans = new int[N];
        count = new int[N];
        list = new ArrayList<List<Integer>>();
        // Arrays.fill（ a1, value ）:a1是一个数组变量，value是一个a1中元素数据类型的值，作用：填充a1数组中的每个元素都是value
        // 将数组count中用1来填充每个值
        Arrays.fill(count, 1);

        for (int i = 0; i < N; i++) {
            list.add(new ArrayList<>());
        }
        // 遍历树结构
        for (int[] edge : edges){
            // 每个数组就是相邻的两个节点
            list.get(edge[0]).add(edge[1]);
            list.get(edge[1]).add(edge[0]);
        }
        // 递归,都是从0开始递归
        sumOfDistancesDfs(0, -1);
        sumOfDistancesDfs2(0, -1);
        return ans;
    }
    // 以root为根节点的遍历，获取整棵树中以0节点为根从上往下遍历中所有子树的subSum值和count值，
    private void sumOfDistancesDfs(int rootIndex, int father) {
        // 从list集合中获取节点
        for (int child : list.get(rootIndex)){
            if (child == father) {
                continue;
            }
            sumOfDistancesDfs(child, rootIndex);
            count[rootIndex] += count[child];
            ans[rootIndex] += ans[child] + count[child];
        }
    }
    // 第二次遍历，我们可以通过上述求得的两个直接相连节点之间的关系从而求得最终我们所要的ans值。
    private void sumOfDistancesDfs2(int rootIndex, int father) {

        for (int child : list.get(rootIndex)){
            if (child == father) {
                continue;
            }
            ans[child] = ans[rootIndex] - count[child] + num - count[child];
            sumOfDistancesDfs2(child, rootIndex);
        }
    }

    /**
     * 二叉树的边界
     * 给定一棵二叉树，以逆时针顺序从根开始返回其边界。边界按顺序包括左边界、叶子结点和右边界而不包括重复的结点。 (结点的值可能重复)
     *
     *  左边界的定义是从根到最左侧结点的路径。右边界的定义是从根到最右侧结点的路径。若根没有左子树或右子树，则根自身就是左边界或右边界。注意该定义只对输入的二叉树
     * 有效，而对子树无效。
     *
     *  最左侧结点的定义是：在左子树存在时总是优先访问，如果不存在左子树则访问右子树。重复以上操作，首先抵达的结点就是最左侧结点。
     *
     *  最右侧结点的定义方式相同，只是将左替换成右。
     *
     *  示例 1
     *
     *  输入:
     *   1
     *    \
     *     2
     *    / \
     *   3   4
     *
     * 输出:
     * [1, 3, 4, 2]
     *
     * 解析:
     * 根不存在左子树，故根自身即为左边界。
     * 叶子结点是3和4。
     * 右边界是1，2，4。注意逆时针顺序输出需要你输出时调整右边界顺序。
     * 以逆时针顺序无重复地排列边界，得到答案[1,3,4,2]。
     *
     *  示例 2
     *  输入:
     *     ____1_____
     *    /          \
     *   2            3
     *  / \          /
     * 4   5        6
     *    / \      / \
     *   7   8    9  10
     *
     * 输出:
     * [1,2,4,7,8,9,10,6,3]
     *
     * 解析:
     * 左边界是结点1,2,4。(根据定义，4是最左侧结点)
     * 叶子结点是结点4,7,8,9,10。
     * 右边界是结点1,3,6,10。(10是最右侧结点)
     * 以逆时针顺序无重复地排列边界，得到答案 [1,2,4,7,8,9,10,6,3]。
     *
     *  Related Topics 树
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    /**
     * 思路：二叉树的”三“视图，左视图+底视图（即全部叶子节点）+右视图，主要是要注意左视图和右视图的定义
     * 左视图的概念：
     * 从根节点一直往左孩子走，左孩子为空，就往右孩子走一步，继续往这个节点的左孩子前进，
     * 再没有就继续右孩子走一步，直到有左孩子或者是叶子节点（有左孩子，就继续往左孩子走了）
     * 左边界是从根到最左侧结点的路径，就是从根节点一直往左孩子走，左孩子为空，就往右孩子走一步，继续往这个节点的左孩子前进，
     * 再没有就继续右孩子走一步，直到有左孩子或者是叶子节点（有左孩子，就继续往左孩子走了），其实说白了，就是沿着最左子树路径一直走，
     * 直到找到第一个叶子节点为止，右视图的概念同理，理解了这个概念，做题目也就不难了。
     * 关于叶子节点视图，因为要保证先左后右的顺序，找叶子节点只能采用先序/中序的遍历方式，才能保证有序。
     * 右视图最后是倒序加入的，需要一个栈来辅助（这里我采用了双端队列来模拟，效果一样），最后加入到结果集中
     *
     */
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        // 判断是否为叶子节点
        if (isLeaf(root)){
            list.add(root.val);
        }
        // 获取左子树节点
        getLeftTree(root, list);
        // 获取叶子节点
        getLeafTree(root, list);
        // 获取右子树节点
        getRightTree(root, list);
        return list;
    }
    // 获取左子树节点
    // 左边界的定义是从根到最左侧结点的路径，所以左视图只要考虑最左路径即可
    private void getLeftTree(TreeNode root, List<Integer> list) {
        if (root == null) return;
        // 左侧节点，往左侧走
        TreeNode left = root.left;
        while (left != null){
            // 判断是否为叶子节点
            // 根节点不是叶子节点才加入，后面叶子节点视图冗余了全部叶子节点
            if (! isLeaf(left)){
                // 当不是叶子节点的时候
                list.add(left.val);
            }
            if (left.left != null){
                // 左子树不为空，继续往左子树走
                left = left.left;
            }else {
                // 否则往右子树走
                left = left.right;
            }
        }
    }
    // 获取叶子节点
    private void getLeafTree(TreeNode root, List<Integer> list) {
        if (root == null) return;
        TreeNode node = root;
        Deque<TreeNode> stack = new LinkedList<>();

        while (node != null || !stack.isEmpty()){
            // 中序遍历（先序遍历也可）
            if (node != null){
                stack.push(node);
                node = node.left;
            }else {
                node = stack.pop();
                if (isLeaf(node)){
                    list.add(node.val);
                }
                node = node.right;
            }

        }
    }
    // 获取右子树节点
    private void getRightTree(TreeNode root, List<Integer> list) {
        if (root == null) return;
        // 右侧往右走
        TreeNode right = root.right;
        // 右子树是要倒序输出，这里用个栈来存储
        Deque<TreeNode> stack = new LinkedList<>();
        while (right != null){
            // 判断是否为叶子节点，不为叶子节点加入到list中
            if (! isLeaf(right)){
                // 将节点加入到栈中
                stack.push(right);
            }
            if (right.right != null){
                right = right.right;
            }else {
                right = right.left;
            }

        }
        // 倒序输出到list集合中
        while (! stack.isEmpty()){
            list.add(stack.pop().val);
        }
    }
    // 判断节点是否叶子节点
    public boolean isLeaf(TreeNode node) {
        // 根据题目要求，得知叶子节点左右子节点均为null
        return node.left == null && node.right == null;
    }

    /**
     * 克隆含随机指针的二叉树
     *
     *  给你一个二叉树，树中每个节点都含有一个附加的随机指针，该指针可以指向树中的任何节点或者指向空（null）。
     *  请返回该树的 深拷贝 。
     *  该树的输入/输出形式与普通二叉树相同，每个节点都用 [val, random_index] 表示：
     *
     *  val：表示 Node.val 的整数
     *  random_index：随机指针指向的节点（在输入的树数组中）的下标；如果未指向任何节点，则为 null 。
     *  该树以 Node 类的形式给出，而你需要以 NodeCopy 类的形式返回克隆得到的树。NodeCopy 类和Node 类定义一致。
     *
     *  示例 1：
     *  输入：root = [[1,null],null,[4,3],[7,0]]
     * 输出：[[1,null],null,[4,3],[7,0]]
     * 解释：初始二叉树为 [1,null,4,7] 。
     * 节点 1 的随机指针指向 null，所以表示为 [1, null] 。
     * 节点 4 的随机指针指向 7，所以表示为 [4, 3] 其中 3 是树数组中节点 7 对应的下标。
     * 节点 7 的随机指针指向 1，所以表示为 [7, 0] 其中 0 是树数组中节点 1 对应的下标。
     *
     *  示例 2：
     *  输入：root = [[1,4],null,[1,0],null,[1,5],[1,5]]
     * 输出：[[1,4],null,[1,0],null,[1,5],[1,5]]
     * 解释：节点的随机指针可以指向它自身。
     *
     *  示例 3：
     *  输入：root = [[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]
     * 输出：[[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]
     *
     *  示例 4：
     *  输入：root = []
     * 输出：[]
     *
     *  示例 5：
     *  输入：root = [[1,null],null,[2,null],null,[1,null]]
     * 输出：[[1,null],null,[2,null],null,[1,null]]
     *
     *  提示：
     *  tree 中节点数目范围是 [0, 1000]
     *  每个节点的值的范围是 [1, 10^6]
     *  Related Topics 树 深度优先搜索
     */
    // TODO：浅拷贝是对于一个对象的顶层拷贝，通俗的理解是：拷贝了引用，并没有拷贝内容
    // 最常用的赋值语句其实就是浅拷贝
    // 深拷贝：是对于一个对象所有层次的拷贝(递归)
    // 深拷贝不仅拷贝了指向，同时也重新开辟了内存空间，把指向的内容拷贝到了新的内存空间中。
//    public class Node {
//        int val;
//        Node left;
//        Node right;
//        Node random;
//        Node() {}
//        Node(int val) { this.val = val; }
//        Node(int val, Node left, Node right, Node random) {
//            this.val = val;
//            this.left = left;
//            this.right = right;
//            this.random = random;
//        }
//    }
//    private Map<Node, NodeCopy> map = new HashMap<>();
//    public NodeCopy copyRandomBinaryTree(Node root) {
//        return NodeDfs(root);
//    }
//
//    private NodeCopy NodeDfs(Node node) {
//        if (node == null) return null;
//        if (map.containsKey(node)){
//            return map.get(node);
//        }else {
//            NodeCopy nodeCopy = new NodeCopy(node.val);
//            map.put(node, nodeCopy);
//            nodeCopy.left = NodeDfs(node.left);
//            nodeCopy.right = NodeDfs(node.right);
//            nodeCopy.random = NodeDfs(node.random);
//            return nodeCopy;
//        }
//    }

    /**
     * 二叉树的右视图
     * 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     *
     *  示例:
     *
     *  输入: [1,2,3,null,5,null,4]
     * 输出: [1, 3, 4]
     * 解释:
     *
     *    1            <---
     *  /   \
     * 2     3         <---
     *  \     \
     *   5     4       <---
     *
     *  Related Topics 树 深度优先搜索 广度优先搜索
     */
    // 广度优先遍历
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size ; i++) {
                TreeNode treeNode = queue.poll();
                if (treeNode.left != null){
                    queue.offer(treeNode.left);
                }
                if (treeNode.right != null){
                    queue.offer(treeNode.right);
                }
                if (i == size - 1){
                    list.add(treeNode.val);
                }
            }
        }
        return list;
    }
    // 深度优先遍历
    List<Integer> integerList = new ArrayList<>();
    public List<Integer> rightSideView2(TreeNode root) {

        rightSideDfs(root, 0);
        return integerList;
    }
    // 递归遍历
    private void rightSideDfs(TreeNode node, int path) {
        if (node == null) return;
        if (path == integerList.size()){
            integerList.add(node.val);
        }
        path ++;
        rightSideDfs(node.right, path);
        rightSideDfs(node.left, path);
    }

    /**
     * 序列化和反序列化二叉搜索树
     * 序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，
     * 以便稍后在同一个或另一个计算机环境中重建。
     *
     *  设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。
     *  您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序
     * 列化为最初的二叉搜索树。
     *  编码的字符串应尽可能紧凑。
     *
     *  示例 1：
     * 输入：root = [2,1,3]
     * 输出：[2,1,3]
     *
     *  示例 2：
     * 输入：root = []
     * 输出：[]
     *
     *  提示：
     *  树中节点数范围是 [0, 104]
     *  0 <= Node.val <= 104
     *  题目数据 保证 输入的树是一棵二叉搜索树。
     *
     *  注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。
     *  Related Topics 树
     */
    // TODO 直接将其用先序遍历序列化，因为是二叉搜索树，所以排序后就是中序遍历，因此反序列化就转换成了105题的从先序与中序构造二叉树的问题。
    class Codec {
        // TODO 思路：
        // 普通的二叉树需要两种遍历结果才能固定二叉树，而对于BST，得到BST的前序遍历，
        // 根据BST的性质，第一个元素值为根节点，小于根节点的元素为左子树，大于根节点的元素为右子树。
        //
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) return "";
            StringBuilder stringBuilder = new StringBuilder();
            preorderTree(root, stringBuilder);
            return stringBuilder.substring(0, stringBuilder.length() - 1);
        }

        private void preorderTree(TreeNode node, StringBuilder stringBuilder) {
            if (node == null) return;
            stringBuilder.append(node.val + ",");
            preorderTree(node.left, stringBuilder);
            preorderTree(node.right, stringBuilder);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) return null;
            String[] strings = data.split(",");
            return buildTree(strings, 0, strings.length - 1);
        }

        private TreeNode buildTree(String[] strings, int start, int end) {
            if (start > end) return null;
            // 构建根节点
            TreeNode root = new TreeNode(Integer.valueOf(strings[start]));
            // TODO 根据BST的性质，第一个元素值为根节点，小于根节点的元素为左子树，大于根节点的元素为右子树。
            int index = end + 1;
            for (int i = start + 1; i <= end; i++) {
                if (Integer.valueOf(strings[i]) > root.val){
                    index = i;
                    break;
                }
            }
            // 递归构建树
            root.left = buildTree(strings, start + 1, index - 1);
            root.right = buildTree(strings, index, end);
            return root;
        }
    }

    /**
     * 二叉树中最大路径和
     *
     * 给定一个非空二叉树，返回其最大路径和。
     *  本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
     *
     *  示例 1：
     *  输入：[1,2,3]
     *
     *        1
     *       / \
     *      2   3
     *
     * 输出：6
     *
     *  示例 2：
     *  输入：[-10,9,20,null,null,15,7]
     *
     *    -10
     *    / \
     *   9  20
     *     /  \
     *    15   7
     *
     * 输出：42
     *  Related Topics 树 深度优先搜索
     */
    private int pathMax = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        // 对于任意一个节点, 如果最大和路径包含该节点, 那么只可能是两种情况:
        // 1. 其左右子树中所构成的和路径值较大的那个加上该节点的值后向父节点回溯构成最大路径
        // 2. 左右子树都在最大路径中, 加上该节点的值构成了最终的最大路径
        getPathMax(root);
        return pathMax;
    }

    private int getPathMax(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, getPathMax(node.left)); // 如果子树路径和为负则应当置0表示最大路径不包含子树
        int right = Math.max(0, getPathMax(node.right));
        pathMax = Math.max(pathMax, node.val + left + right); // 判断在该节点包含左右子树的路径和是否大于当前最大路径和
        return Math.max(left, right) + node.val;
    }

    /**
     * 矩阵中的最长递增路径
     * 给定一个整数矩阵，找出最长递增路径的长度。
     *
     * 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
     *
     * 示例 1:
     * 输入: nums =
     * [
     *   [9,9,4],
     *   [6,6,8],
     *   [2,1,1]
     * ]
     * 输出: 4
     * 解释: 最长递增路径为 [1, 2, 6, 9]。
     *
     * 示例 2:
     * 输入: nums =
     * [
     *   [3,4,5],
     *   [3,2,6],
     *   [2,2,1]
     * ]
     * 输出: 4
     * 解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
     *
     */
    // TODO 采用DFS + 备忘录，记录已经遍历过的节点
    // 解题思路
    // 原理就是查询每个数四周的数，找到四周比它小的数的最大连续增长长度，而四周比它小的数递归，继续
    // 这种操作，直到找到能返回一个最大连续增长长度
    // 而查询数四周比它小的数的最大增长长度+1就是查询数的最大增长长度
    // 然后对每个数的最大增长长度进行比较
    // 得到该矩形格的最大增长长度
    //
    public int longestIncreasingPath(int[][] matrix) {

        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return 0;
        // 行
        int row = matrix.length;
        // 列
        int clo = matrix[0].length;
        // 节点最长路径
        int max = 0;
        // 备忘录，记录已经遍历过的节点
        // 1.判断是否访问过，2.存储当前格子的最长递增长度
        int[][] dp = new int[row][clo];
        // 遍历矩形中的节点
        // 遍历------将每个数的最大增长长度遍历出来，然后筛选出最大的
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < clo; j++) {
                if (dp[i][j] == 0) {
                    // 比较找出max，可以避免最后再去遍历一遍dp数组
                    max = Math.max(max, matrixPathMax(matrix, i, j, dp));
                }

            }
        }
        return max;
    }

    private int matrixPathMax(int[][] matrix, int i, int j, int[][] dp) {
        // 行
        int row = matrix.length;
        // 列
        int clo = matrix[0].length;
        // 对边界进行判断
        if (i < 0 || i >= row || j < 0 || j >= clo ) return 0;
        // 该数已经存储了最大增长长度，直接返回
        if (dp[i][j] != 0) {
            // 表示该数已经访问过
            return dp[i][j];
        }
        int max = 0;

        //这里分别去判断4周是否比当前数小，然后去递归遍历
        //直到遍历出当前值的四周比它小的数当中的最大的连续增长值
        //然后连续增长值+1就是当中数的连续增长
        //递归过程当中得到的数的连续增长值，存储在dp[]数组当中

        // 当前节点往左侧移动
        if (i - 1 >= 0 && matrix[i - 1][j] < matrix[i][j]){
            max = Math.max(max, matrixPathMax(matrix, i - 1, j, dp));
        }
        // 当前节点往右侧移动
        if (i + 1 < row && matrix[i + 1][j] < matrix[i][j]){
            max = Math.max(max, matrixPathMax(matrix, i + 1, j, dp));
        }
        // 当前节点往上侧移动
        if (j - 1 >= 0 && matrix[i][j - 1] < matrix[i][j]){
            max = Math.max(max, matrixPathMax(matrix, i , j - 1, dp));
        }
        // 当前节点往下侧移动
        if (j + 1 < clo && matrix[i][j + 1] < matrix[i][j]){
            max = Math.max(max, matrixPathMax(matrix, i, j + 1, dp));
        }
        //得到的最大的增长长度加一就是当前数的最大增长度
        dp[i][j] = max + 1;
        return max + 1;
    }

    /**
     * 监控二叉树
     *
     *  给定一个二叉树，我们在树的节点上安装摄像头。
     *  节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
     *  计算监控树的所有节点所需的最小摄像头数量。
     *
     *  示例 1：
     *  输入：[0,0,null,0,0]
     *  输出：1
     *  解释：如图所示，一台摄像头足以监控所有节点。
     *
     *
     *  示例 2：
     *  输入：[0,0,null,0,null,0,null,null,0]
     * 输出：2
     * 解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
     *
     * 提示：
     *  给定树的节点数的范围是 [1, 1000]。
     *  每个节点的值都是 0。
     *
     *  Related Topics 树 深度优先搜索 动态规划
     */
    // TODO 0未覆盖，1被覆盖，2安装了相机
    int cameraNum;
    public int minCameraCover(TreeNode root) {
        if (root == null) return 0;
        int last = cameraDfs(root);
        if(last == 0){
            cameraNum ++;
            return cameraNum;
        }
        return cameraNum;
    }

    private int cameraDfs(TreeNode node) {
        // 如果节点为空，说明是被覆盖了
        if (node == null) return 1;
        // 获取子节点情况
        int left = cameraDfs(node.left);
        int right = cameraDfs(node.right);
        // 如果两个子节点都是1，说明子节点不存在或者子节点被其它相机覆盖了
        // 那么为了相机最小化，当前节点不能有相机，需要被它的父节点覆盖
        // 都为1的情况需要告知父节点安装
        if (left == 1 && right == 1) return 0;
        // 如果子节点都是0，表示它们等待被覆盖，那么当前节点就要安装相机
        if (left == 0 || right == 0) {
            cameraNum ++;
            return 2;
        }
        // 只要子节点任何一个节点安装了相机，那么当前节点就是被覆盖的
        if (left == 2 || right == 2){
            return 1;
        }
        return 1;
    }

    /**
     * 可能的二分法
     *
     * 给定一组 N 人（编号为 1, 2, ..., N）， 我们想把每个人分进任意大小的两组。
     *  每个人都可能不喜欢其他人，那么他们不应该属于同一组。
     *  形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。
     *  当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。
     *
     *  示例 1：
     * 输入：N = 4, dislikes = [[1,2],[1,3],[2,4]]
     * 输出：true
     * 解释：group1 [1,4], group2 [2,3]
     *
     *  示例 2：
     * 输入：N = 3, dislikes = [[1,2],[1,3],[2,3]]
     * 输出：false
     *
     *  示例 3：
     * 输入：N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
     * 输出：false
     *
     *  提示：
     *  1 <= N <= 2000
     *  0 <= dislikes.length <= 10000
     *  dislikes[i].length == 2
     *  1 <= dislikes[i][j] <= N
     *  dislikes[i][0] < dislikes[i][1]
     *  对于 dislikes[i] == dislikes[j] 不存在 i != j
     *
     *  Related Topics 深度优先搜索 图
     */
    // TODO BFS染色法 : 本质上就是看相邻的两个点是不是能够染成不同的颜色
    //  /*
    //	 * 0代表要染成的颜色是不喜欢的人
    //	 * 1代表要染成的颜色是不喜欢的人
    //	 * 说明当中已经有结点被染过色， 且是不喜欢的人
    //	 */
    // 本题类似于经典的染色算法，使用DFS（深度遍历）思路解题（不知的这个的自行百度，类似走迷宫的思想），
    // 首先将限制条件转换为一个图，将color[] 赋予初始值-1，color的长度为可以使用颜色的数量。
    //（本做法首先要理解：题目给出的N相当于，给出了N个节点，每个节点一个颜色，所以共有N个节点，N个颜色。我们是在此前提下，判断 “不允许分组”构成的图，判断相邻的两个节点是否不同颜色）
    // TODO DFS思路：
    //染色的过程是第一圈，第二圈，第三圈......以此类推进行染色判定
    //遍历所有节点的过程，对其进行染色标记，第一圈为 0 ，第二圈为 1-0，第三圈为1-（1-0）=0 ， 第四圈为 1-0 其实是相邻的两圈进行判断，
    // 若Q1 = Q2 则说明在N个颜色的条件下，无法满足对限制条件图进行染色判定。
    //进行深度遍历时，若节点未进行染色判定，进行染色判定，直到到达最后一个节点，没有下一个节点时返回true，（途中染色判定失败直接返回）。
    //当所有节点都进行染色判定后，途中没有失败时，说明条件可以进行二分算法。
    // 记录
    Map<Integer, List<Integer>> possibleMap = new HashMap<>();
    // 记录每个节点颜色
    int[] color;
    public boolean possibleBipartition(int N, int[][] dislikes) {
        color = new int[N + 1];
        Arrays.fill(color, -1);
        for (int i = 1; i <= N; i++) {
            possibleMap.put(i, new ArrayList<>());
        }
        // 将图存入
        for (int[] dislike : dislikes){
            int from = dislike[0];
            int to = dislike[1];
            possibleMap.get(from).add(to);
            possibleMap.get(to).add(from);
        }

        for (int i = 1; i <= N; i ++){
            if (color[i] < 0){
                color[i] = 0;
                if (!possibleDfs(i)) {
                    return false;
                }
            }
        }
        return true;
    }
    // 对节点依次进行深搜，判断是否已经染色，且染色是否正确
    private boolean possibleDfs(int current) {

        for (int next : possibleMap.get(current)){
            if (color[next] < 0){
                color[next] = 1 - color[current];
                if (!possibleDfs(next)){
                    return false;
                }
            }else if (color[next] == color[current]){
                return false;
            }
        }
        return true;
    }


    /**
     * 喧闹和富有
     *
     * 在一组 N 个人（编号为 0, 1, 2, ..., N-1）中，每个人都有不同数目的钱，以及不同程度的安静（quietness）。
     *  为了方便起见，我们将编号为 x 的人简称为 "person x "。
     *  如果能够肯定 person x 比 person y 更有钱的话，我们会说 richer[i] = [x, y] 。注意 richer 可能只是有效观察的
     * 一个子集。
     *  另外，如果 person x 的安静程度为 q ，我们会说 quiet[x] = q 。
     *  现在，返回答案 answer ，其中 answer[x] = y 的前提是，在所有拥有的钱不少于 person x 的人中，person y 是最安静的人
     * （也就是安静值 quiet[y] 最小的人）。
     *
     *  示例：
     *  输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1
     * ,7,0]
     * 输出：[5,5,2,5,4,5,6,7]
     * 解释：
     * answer[0] = 5，
     * person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。
     *
     * 唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7，
     * 但是目前还不清楚他是否比 person 0 更有钱。
     *
     * answer[7] = 7，
     * 在所有拥有的钱肯定不少于 person 7 的人中(这可能包括 person 3，4，5，6 以及 7)，
     * 最安静(有较低安静值 quiet[x])的人是 person 7。
     *
     * 其他的答案也可以用类似的推理来解释。
     *
     *  提示：
     *  1 <= quiet.length = N <= 500
     *  0 <= quiet[i] < N，所有 quiet[i] 都不相同。
     *  0 <= richer.length <= N * (N-1) / 2
     *  0 <= richer[i][j] < N
     *  richer[i][0] != richer[i][1]
     *  richer[i] 都是不同的。
     *  对 richer 的观察在逻辑上是一致的。
     *
     *  Related Topics 深度优先搜索
     *  TODO 这里需要深入理解图的数据结构
     */
    // 思路：
    //如果 y 比 x 富有，就认为在有向图中存在边 x -> y 。
    //对每个 x（也就是每个人），我们都希望最安静的人就在 x 的子树中。
    //
    //算法：
    //构建上面所描述的图，并且 dfs(person) 是 person 的子树上最安静的人。注意，因为语句在逻辑上是一致的，所以图必须是有向无环图（即，DAG）—— 任意一条边都有方向，且不存在环路的图。
    //现在 dfs(person) 既可以是 person 本身，也可以是 min(dfs(child)) 。也就是说，子树中最安静的人可以是 person 本身，或者是 person 的子结点的某个子树中最安静的人。
    //当执行图的 后序遍历 时，我们可以将 dfs(person) 的值缓存为 answer[person] 。这样，我们就不会重复工作。该技巧有助于将算法的时间复杂度从平方阶降低到线性阶。

    // 有向图
    ArrayList<Integer>[] graph;
    // 存储结果数组
    int[] answer;
    // 安静数组
    int[] quiet;
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        // 人数
        int N = quiet.length;
        answer = new int[N];
        graph = new ArrayList[N];
        this.quiet = quiet;
        // 初始化有向图
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        // 将富有值放入
        for(int[] rich : richer){
            graph[rich[1]].add(rich[0]);
        }
        // 将answer数组填充
        Arrays.fill(answer, -1);
        for (int i = 0; i < N; i++) {
            loudAndRichDfs(i);
        }
        return answer;
    }

    private int loudAndRichDfs(int person) {
        if (answer[person] == -1){
            answer[person] = person;
            for (int child : graph[person]){
                // 递归子节点
                int next = loudAndRichDfs(child);
                if (quiet[next] < quiet[answer[person]]){
                    answer[person] = next;
                }
            }
        }
        return answer[person];
    }

    /**
     * 多线程网页爬虫
     *
     * 给你一个初始地址 startUrl 和一个 HTML 解析器接口 HtmlParser，请你实现一个 多线程的网页爬虫，用于获取与 startUrl 有 相
     * 同主机名 的所有链接。
     *
     *  以 任意 顺序返回爬虫获取的路径。
     *
     *  爬虫应该遵循：
     *
     *
     *  从 startUrl 开始
     *  调用 HtmlParser.getUrls(url) 从指定网页路径获得的所有路径。
     *  不要抓取相同的链接两次。
     *  仅浏览与 startUrl 相同主机名 的链接。
     *
     *  如上图所示，主机名是 example.org 。简单起见，你可以假设所有链接都采用 http 协议，并且没有指定 端口号。举个例子，链接 http://l
     * eetcode.com/problems 和链接 http://leetcode.com/contest 属于同一个 主机名， 而 http://example
     * .org/test 与 http://example.com/abc 并不属于同一个 主机名。
     *
     *  HtmlParser 的接口定义如下：
     *
     *
     * interface HtmlParser {
     *   // Return a list of all urls from a webpage of given url.
     *   // This is a blocking call, that means it will do HTTP request and return wh
     * en this request is finished.
     *   public List<String> getUrls(String url);
     * }
     *
     *  注意一点，getUrls(String url) 模拟执行一个HTTP的请求。 你可以将它当做一个阻塞式的方法，直到请求结束。 getUrls(Strin
     * g url) 保证会在 15ms 内返回所有的路径。 单线程的方案会超过时间限制，你能用多线程方案做的更好吗？
     *
     *  对于问题所需的功能，下面提供了两个例子。为了方便自定义测试，你可以声明三个变量 urls，edges 和 startUrl。但要注意你只能在代码中访问 s
     * tartUrl，并不能直接访问 urls 和 edges。
     *
     *  拓展问题：
     *  假设我们要要抓取 10000 个节点和 10 亿个路径。并且在每个节点部署相同的的软件。软件可以发现所有的节点。我们必须尽可能减少机器之间的通讯，并确保每
     * 个节点负载均衡。你将如何设计这个网页爬虫？
     *  如果有一个节点发生故障不工作该怎么办？
     *  如何确认爬虫任务已经完成？
     *
     *  示例 1：
     * 输入：
     * urls = [
     *   "http://news.yahoo.com",
     *   "http://news.yahoo.com/news",
     *   "http://news.yahoo.com/news/topics/",
     *   "http://news.google.com",
     *   "http://news.yahoo.com/us"
     * ]
     * edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
     * startUrl = "http://news.yahoo.com/news/topics/"
     * 输出：[
     *   "http://news.yahoo.com",
     *   "http://news.yahoo.com/news",
     *   "http://news.yahoo.com/news/topics/",
     *   "http://news.yahoo.com/us"
     * ]
     *
     *
     *  示例 2：
     *
     *
     *
     *
     * 输入：
     * urls = [
     *   "http://news.yahoo.com",
     *   "http://news.yahoo.com/news",
     *   "http://news.yahoo.com/news/topics/",
     *   "http://news.google.com"
     * ]
     * edges = [[0,2],[2,1],[3,2],[3,1],[3,0]]
     * startUrl = "http://news.google.com"
     * 输出：["http://news.google.com"]
     * 解释：startUrl 链接与其他页面不共享一个主机名。
     *
     *
     *
     *  提示：
     *
     *
     *  1 <= urls.length <= 1000
     *  1 <= urls[i].length <= 300
     *  startUrl 是 urls 中的一个。
     *  主机名的长度必须为 1 到 63 个字符（包括点 . 在内），只能包含从 “a” 到 “z” 的 ASCII 字母和 “0” 到 “9” 的数字，以及中划
     * 线 “-”。
     *  主机名开头和结尾不能是中划线 “-”。
     *  参考资料：https://en.wikipedia.org/wiki/Hostname#Restrictions_on_valid_hostnames
     *  你可以假设路径都是不重复的。
     *
     *  Related Topics 深度优先搜索 广度优先搜索
     */
    public List<String> crawl(String startUrl, HtmlParser htmlParser) {
        return null;
    }
    interface HtmlParser {
      public List<String> getUrls(String url);
    }





















}
